package leetcode.hot100;

public class Solution338 {

    public static void main(String[] args) {

        new Solution338().countBits(20);

    }


    public int[] countBits1(int num) {
        if(num==0) return new int[1];
        int[] res = new int[num+1];
        res[1] = 1;
        //2^k为一轮，此轮的数值是上一轮2^(k-1)个的复制和自增
        //用i表示当前要填充的位置，epoch表示2^(k-1)，count记录本轮填充了多少数字，start记录上一轮开始的位置
        //初始化,从k=2开始填充
        int i = 2, epoch = 1, count = 0, start = 1;
        while (i<=num){
            if(count<epoch){ //填充的是2^k中的前半段
                res[i] = res[start+count];
                count++;
                i++;
            }else if(count<epoch*2){ //填充的是2^k的后半段,由于前半段和上一轮数字相同，可以让count继续走
                res[i] = res[start+count]+1;
                count++;
                i++;
            }else { //2^k数都添上了，本轮完毕
                count = 0;
                start += epoch;
                epoch <<= 1;
            }
        }
        return res;
    }

    public int[] countBits(int num) {
        int[] res = new int[num+1];
        for (int i = 1; i <= num; i++) {
            res[i] = res[i&(i-1)]+1;
        }
        return res;
    }
}
